package leetcode_core.leetcode_6;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月14日 22:31
 */
public class CharacterReplacement {
    public int characterReplacement(String s, int k) {
        int[] memo = new int[26];
        //初始化窗口
        char[] str = s.toCharArray();
        int left = 0,right = 0,length = str.length;
        memo[str[left]-'A']++;
        //首先需要搞清楚合法窗口的长度最多是多少?
        //假设我们在当前的窗口中,能够检查出来的原生相同子串的长度是maxLengthInWindow
        //那么我们有k个机会,在区间`[left,right]`中,形成最大的相同子串长度是maxLengthInWindow+k
        //因此,当[left,right]区间中的元素个数是小于maxLengthWindow+k的时候,我们就可以扩张窗口
        //写成不等式就是right-left-1 <= maxLengthWindow+k
        //这里有个边界需要讨论一下哈
        //就是right-left-1 = maxLength+k的时候,这时候是个啥情况?
        //这个问题必须搞清楚,就是理论上这个点是否是扩张窗口的点?
        int maxLengthInWindow = 0;
        while(right < str.length){
            //向右扩张窗口
            memo[str[right]-'A']++;
            maxLengthInWindow = Math.max(maxLengthInWindow,memo[str[right]-'A']);
            right++;
            if(right-left-1 > maxLengthInWindow+k){
                memo[str[left]]--;
                left++;
            }
        }
        return str.length-left;
    }
}
